package class06_heap;

public class Test02_Heap {

    public class MyMaxHeap {
        // 容器
        private int[] heap;
        // 限制
        private int limit;
        // 堆长度
        private int heapSize;

        //构造器
        public MyMaxHeap(int limit) {
            this.heap = new int[limit];
            this.limit = limit;
            heapSize = 0;
        }

        /**
         * 堆是否为空
         */
        public boolean isEmpty() {
            return heapSize == 0;
        }

        /**
         * 堆是否满了
         */
        public boolean isFull() {
            return heapSize == limit;
        }

        /**
         * 往堆中push数据,并且维持大根堆
         */
        public void push(int value) {
            // 边界判断
            if (isFull()) {
                throw new RuntimeException("堆已经满了");
            }
            // 1、将value加入数组末尾
            heap[heapSize] = value;
            //２、调整数组形态，维持大根堆
            heapInsert(heap, heapSize++);
        }

        /**
         * 弹出堆中最大是数据，并且在堆中将最大值删除
         */
        public int pop() {
            if (isEmpty()) {
                throw new RuntimeException("堆已经空了");
            }
            int ans = heap[0];
            swap(heap, 0, --heapSize);
            heapify(heap, 0, heapSize);
            return ans;
        }

    }

    /**
     * 从上往下调，堆的大小为 heapSize
     *
     * @param heap
     * @param index
     * @param heapSize
     */
    private void heapify(int[] heap, int index, int heapSize) {
        int left = 2 * index + 1;
        // 确定左子节点索引位置
        // 当 index < heapSize 时，就一直往下沉，当 index 位置不比他的（较大子节点）小了，或者等于他的（较大子节点）了，就停止循环
        while (index < heapSize) {
            // 找出父子节点中值最大的索引位置
            int largest = (left + 1) < heapSize && heap[left] < heap[left + 1] ? left + 1 : left;
            largest = heap[index] > heap[largest] ? index : largest;
            if (largest == index) {
                break;
            }
            swap(heap, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    /**
     * 从下往上调，
     *
     * @param heap
     * @param index
     */
    private void heapInsert(int[] heap, int index) {
        while (heap[index] > heap[(index - 1) / 2]) {
            swap(heap, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 交换两个元素的位置
     *
     * @param heap
     * @param i
     * @param j
     */
    private void swap(int[] heap, int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

}
